/* Archivo de encabezamiento: 
*/

#include "list-ch.h"

#ifndef _GRAPH_CONLISTA_H
#define _GRAPH_CONLISTA_H


#define LENGHT_ALFABETH 27

typedef struct graphCDT *graphADT;

typedef int * state; 

typedef struct elementoMioDelNodo
{
	int state_id[LENGHT_ALFABETH];
	int isFinalState;
	listADT wordList;
}elementoMioDelNodo;

typedef elementoMioDelNodo* elementT;

typedef char elementEdge;

typedef struct adyacentNode
{
	elementT node;
	elementEdge value;
}adyacentNode;


typedef elementoMioDelNodo* nodeState; 







/* Funcion: newGraph
* Uso: 
* graphADT grafo;
* grafo=newGraph(funcion);
* -------------------------------------------------------------------
* Descripci�n: Inicializa el grafo y setea la funci�n de
* comparaci�n para sus elementos. Dicha funci�n
* compara dos elementos de tipo ElementT
* y debe devolver un n�mero negativo si el primer
* argumento debe aparecer antes que el segundo,
* un n�mero positivo si debe aparecer despu�s �
* 0 si se trata del mismo elemento.
* Usarla una sola vez antes de empezar
* a usar el resto de las operaciones.
* Devuelve NULL si no se pudo alocar memoria..
* -------------------------------------------------------------------
* Precondicion: Funci�n distinta de NULL
* Postcondicion: grafo creada.
*/
graphADT
newGraph(int (*fn) (void* element1, void* element2));

/* Funcion: graphIsEmpty
* Uso: if ( graphIsEmpty( grafo ) ...
* -------------------------------------------------------------------
* Descripci�n: Devuelve 1 si el grafo est� vac�o o
* cero en caso contrario
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: - (lista invariante).
*/
int graphIsEmpty(graphADT graph);

/* Funcion: duplicateGraph
* graphADT grafo,copia;
* grafo=newGraph(funcion);
* ...
* if ((copia=duplicateGraph(grafo)!=NULL)
*     printf("Copia exitosa");
* -------------------------------------------------------------------
* Descripci�n: Hace una nueva instancia del grafo.
* Devuelve el grafo copiado o en caso de error, devuelve NULL.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, Grafo copia definido.
* Postcondicion: Copia exacta del grafo.
*/
graphADT duplicateGraph(graphADT graph);

/* Funcion: addNode
* Uso: int nro= 4;
* addNode( grafo, nro );
* -------------------------------------------------------------------
* Descripci�n: Inserta un nodo en la grafo con el elemento deseado,
* usando la funci�n de comparaci�n seteada en
* la creaci�n del grafo. 
* Si el elemento ya exist�a, lo ignora.
* Si hay problemas en la alocaci�n de memoria
* finaliza la aplicaci�n.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: Grafo con el nuevo nodo,
* si no estaba repetido.
*/
int addNode(graphADT graph, elementT element);

/* Funcion: deleteNode
* Uso: int nro= 4;
* deleteNode( grafo, nro );
* -------------------------------------------------------------------
* Descripci�n: Elimina el elemento del grafo,
* usando la funci�n de comparaci�n seteada en la
* creaci�n del grafo. Si el elemento
* no exist�a devuelve 0, caso contrario 1
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: Grafo sin ese nodo
*/
int deleteNode(graphADT graph, elementT element);

/* Funcion: nodeExists
* Uso: int nro= 4;
* ....
* if (nodeExists(grafo, nro))
*   ....
* -------------------------------------------------------------------
* Descripci�n: Retorna 1 si el nodo mandado
* existe en el grafo, y 0 en caso contrario
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: -.
*/
int nodeExists(graphADT graph,elementT element);

/* Funcion: getAdyacents
* Uso: int nro= 4,*vec,i;
*	vec=getAdyacents(grafo,nro);
*
*	printf("\n\nAdyacentes a %d:",nro);
*	for(i=0;i<gradeNode(grafo,nro);i++)
*	{
*		printf("%d ",vec[i]);
*	}
*	free(vec);
*
* -------------------------------------------------------------------
* Descripci�n: Obtiene un vector con los nodos
* adyacentes a ese nodo pedido. El vector de elementos
* debe ser liberado por el usuario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existente, puntero
* a vector de elementos.
* Postcondicion: Vector con nodos adyacentes al nodo en cuestion, 
* memoria alocada en el puntero. 
*/
adyacentNode* getAdyacents(graphADT graph, elementT element);

/* Funcion: getNodes
* Uso: int i,*vec;
*	vec=getNodes(grafo);
*
*	printf("Nodos del Grafo:");
*	for(i=0;i<countNodes(grafo);i++)
*	{
*		printf("%d ",vec[i]);
*	}
*	free(vec);
*
* -------------------------------------------------------------------
* Descripci�n: Obtiene un vector con los nodos
* del grafo. El vector de elementos debe ser 
* liberado por el usuario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: Vector con nodos del grafo, memoria
* alocoda.
*/
elementT* getNodes(graphADT graph);

/* Funcion: addEdge
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* -------------------------------------------------------------------
* Descripci�n: Inserta una arista en la grafo 
* entre los elementos deseados.
* Si hay problemas en la alocaci�n de memoria
* finaliza la aplicaci�n. Devuelve 1 si la
* arista fue creada exitosamente
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes
* Postcondicion: Grafo con una arista que une los
* nodos deseados y la arista logica creada.
*/
int addEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge element);

/* Funcion: deleteEdge
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* deleteEdge(grafo,nro,nro2);
* -------------------------------------------------------------------
* Descripci�n: Borra una arista en la grafo 
* entre los elementos deseados.
* Si hay problemas en la alocaci�n de memoria
* finaliza la aplicaci�n. Devuelve 1 si la
* arista fue eliminada exitosamente
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes
* Postcondicion: Grafo con sin la arista fisica y logica que une los
* nodos deseados
*/
int deleteEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge);

/* Funcion: edgeExists
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* if(edgeExists(grafo,nro))
*      ...
* -------------------------------------------------------------------
* Descripci�n: Checkea si existe una arista 
* entre los nodos.
* Devuelve 1 si existe la arista, 0 en caso contrario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes
* Postcondicion: -
*/
int edgeExists(graphADT graph, elementT elFrom, elementT elTo, elementEdge element);

/* Funcion: markEdge
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* markEdge(grafo,nro,nro2);
*      ...
* -------------------------------------------------------------------
* Descripci�n: Borra la arista del grafo logicamente
* sin borrarla en la memoria.
* Devuelve 1 si la borra exitosamente, 0 en caso contrario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes,
* arista entre ambos nodos.
* Postcondicion: Arista borrada logicamente.
*/
int markEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge);

/* Funcion: unmarkEdge
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* unmarkEdge(grafo,nro,nro2);
*      ...
* -------------------------------------------------------------------
* Descripci�n: Restaura la arista del grafo logicamente
* sin agregarla en la memoria.
* Devuelve 1 si la restaura exitosamente, 0 en caso contrario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes,
* arista entre ambos nodos.
* Postcondicion: Arista restaurada logicamente.
*/
int unmarkEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge);

/* Funcion: edgeIsMarked
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* if (edgeIsMarked(grafo,nro,nro2))
*      ...
* -------------------------------------------------------------------
* Descripci�n: Devuelve si existe una arista logica entre
* ambos nodos.
* Devuelve 1 si existe, 0 en caso contrario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes,
* arista entre ambos nodos.
* Postcondicion: -
*/
int edgeIsMarked(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge);

/* Funcion: markNode
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* ...
* markNode(grafo,nro);
*      ...
* -------------------------------------------------------------------
* Descripci�n: Devuelve si el nodo esta marcado
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existente
* Postcondicion: -.
*/
int markNode(graphADT graph, elementT element);

/* Funcion: unmarknode
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro2 );
* ...
* unmarkNode(grafo,nro2);
*      ...
* -------------------------------------------------------------------
* Descripci�n: Desmarca el nodo seleccionado
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existente
* Postcondicion: Nodo marcado.
*/
int unmarkNode(graphADT graph, elementT element);

/* Funcion: nodeIsMarked
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* ...
*
* if (nodeIsMarked(grafo,nro))
*      ...
* -------------------------------------------------------------------
* Descripci�n: Devuelve si el nodo esta marcado.
* Devuelve 1 si lo esta, 0 en caso contrario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existente.
* Postcondicion: -
*/
int nodeIsMarked(graphADT graph, elementT element);

/* Funcion: setWeight
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* setWeight(grafo, nro, nro2, 5);
* -------------------------------------------------------------------
* Descripci�n: Le pone un peso a la arista en cuestion.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos y arista 
* existentes.
* Postcondicion: Peso asignado a la arista.
*/
int setWeight(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge, int weight);

/* Funcion: getWeight
* Uso: ...
* setWeight(grafo, nro, nro2, 5);
* ...
* getWeight(grafo, nro, nro2);
* -------------------------------------------------------------------
* Descripci�n: Devuelve el peso la arista en cuestion.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos y arista 
* existentes, peso asignado.
* Postcondicion: Obtencion del peso de la arista.
*/
int getWeight(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge);


/* Funcion: gradeNode
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* addEdge(grafo,nro,nro2);
* ...
* printf("Grado del Nodo=%d",gradeNode(grafo,nro));
* -------------------------------------------------------------------
* Descripci�n: Devuelve el grado del nodo.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existente.
* Postcondicion: Entero con el grado del nodo.
*/
int gradeNode(graphADT graph, elementT element);

/* Funcion: countNodes
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* ...
* printf("Cantidad de nodos del grafo=%d",countNodes(grafo));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de nodos del grafo.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: Entero con la cantidad de nodos.
*/
int countNodes(graphADT graph);

/* Funcion: countEdges
* Uso: int nro= 4, nro2=2;
* addNode( grafo, nro );
* addNode( grafo, nro2 );
* ...
* printf("Cantidad de aristas del grafo=%d",countEdges(grafo));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de aristas del grafo.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: Entero con la cantidad de aristas.
*/
int countEdges(graphADT graph);


/* Funcion: graphDFS
* Uso: graphADT grafo, gDFS;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
*
* gDFS=graphDFS(grafo,2);
* -------------------------------------------------------------------
* Descripci�n: Devuelve un el grafo DFS creado a partir
* del grafo enviado desde el nodo pedido. Si hubo algun
* error devuelve NULL.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existente.
* Postcondicion: grafo DFS del grafo.
*/
graphADT
graphDFS(graphADT gOriginal, elementT nodeFrom);

/* Funcion: countEdgesComponent
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
*
* printf("La cantidad de aristas del componente que_ 
   contiene a 1 es %d\n",countEdgesComponent(grafo, 1));
* ...
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de aristas de la componente
* que contiene a nodeFrom. Si el grafo es conexo, entonces
* devuelve la cantidad de aristas totales.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existente.
* Postcondicion: Cantidad de aristas de la componente.
*/
int
countEdgesComponent(graphADT graph, elementT nodeFrom);

/* Funcion: pathExists
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
*
* if (pathExists(grafo, nro, 5))
*      .....
* -------------------------------------------------------------------
* Descripci�n: Devuelve 1 si existe algun camino entre el nodo
* From y el nodo To. 0 En caso contrario.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes.
* Postcondicion: -.
*/
int
pathExists(graphADT graph, elementT elFrom, elementT elTo);

/* Funcion: freeGraph
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
* freeGraph(grafo);
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de nodos del grafo.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado
* Postcondicion: Entero con la cantidad de nodos.
*/
void freeGraph(graphADT graph);

/* Funcion: shortestPath
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
* printf("El camino minimo entre 2 y 4 es %d",shortestPath(grafo, 2,4));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad minima de aristas que une ambos nodos.
* Si los nodos no estan conectados, devuelve 0..
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes.
* Postcondicion: Entero con la cantidad de minima de aristas que los une.
*/
int
shortestPath(graphADT graph, elementT nodeFrom, elementT nodeTo);

/* Funcion: poundingShortestPath
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
* printf("El camino minimo entre 2 y 4 es %d",shortestPath(grafo, 2,4));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad minima de aristas que une ambos nodos
* ponderando las aristas.
* Si los nodos no estan conectados, devuelve 0. Si hubo algun error, -1.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes.
* Postcondicion: Entero con la cantidad de minima de aristas que los une con
* ponderacion..
*/
int
poundingShortestPath(graphADT graph, elementT nodeFrom, elementT nodeTo);

/* Funcion: countEdgesComponent
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
* printf("La cantidad de aristas que se pueden alcanzar desde_
* el nodo 2 es %d",countEdgesComponent(grafo, 2));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de aristas que se pueden
* alcanzar desde el nodo 2.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodo existentes.
* Postcondicion: Entero con la cantidad de aristas.
*/
int
countEdgesComponent(graphADT graph, elementT nodeFrom);

/* Funcion: longestPathWithoutNode
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
* printf("El camino minimo entre 2 y 4 es %d",shortestPath(grafo, 2,4));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de aristas del camino mas
* largo que se pueda lograr excluyendo al nodo pedido. Si el camino es
* invalido devuelve 0. Si existio un error devuelve -1.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes.
* Postcondicion: Entero con la cantidad de aristas que une el camino mas
* largo entre nodeFrom y nodeExclude.
*/
int
longestPathWithoutNode(graphADT graph, elementT nodeFrom, elementT nodeExclude);

/* Funcion: longestPath
* Uso: graphADT grafo;
* int nro=2;
* grafo=newGraph(fn);
* addNode( grafo, nro );
* ...
* printf("La cantidad de aristas que contiene camino maximo que se puede _
* lograr desde 1 es ",longestPath(grafo,1));
* -------------------------------------------------------------------
* Descripci�n: Devuelve la cantidad de aristas del camino mas
* largo que se pueda lograr desde el nodo pedido.. Si el camino es
* invalido devuelve 0. Si existio un error devuelve -1.
* -------------------------------------------------------------------
* Precondicion: Grafo valido previamente creado, nodos existentes.
* Postcondicion: Entero con la cantidad de aristas que une el camino mas
* largo que se pueda lograr desde el nodeFrom.
*/
int
longestPath(graphADT graph, elementT nodeFrom);

#endif
